package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Description: 647. 回文子串
 *
 * @author weiruibai.vendor
 * Date: 2022/11/7 14:11
 */
public class Solution_647 {


    public static void main(String[] args) {
        Solution_647 instance = new Solution_647();
        String s = "abc";
        s = "aaa";
        s = "fdsklf";
        s = "longtimenosee";
        s = "xkjkqlajprjwefilxgpdpebieswu";
        s = "dnncbwoneinoplypwgbwktmvkoimcooyiwirgbxlcttgteqthcvyoueyftiwgwwxvxvg";
        // s = "";
        // System.out.println(s.length());
        System.out.println(instance.countSubstrings(s) + " times: " + atom2.get());
        System.out.println(instance.countSubstrings_dp(s) + " times: " + atom2.get());
    }

    static AtomicInteger atom = new AtomicInteger(0);
    static AtomicInteger atom2 = new AtomicInteger(0);

    /**
     * 中心扩展法
     * 1、一个中点两边扩展 eg:aba b两边扩展
     * 2、两个相邻点同时两边扩展 eg: aab 位置0，1两边扩展
     *
     * @param s
     * @return
     */
    public int countSubstrings_dp(String s) {

        int n = s.length();
        int ans = 0;
        for (int center = 0; center < n; center++) {
            ans += expand(s, center, center);
            ans += expand(s, center, center + 1);
        }
        return ans;
    }

    private int expand(String s, int left, int right) {
        int ans = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            atom.incrementAndGet();
            ans++;
            left--;
            right++;
        }
        return ans;
    }

    /**
     * 超时
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, List<Integer>> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            List<Integer> orDefault = map.getOrDefault(chars[i], new ArrayList<>());
            orDefault.add(i);
            map.put(chars[i], orDefault);
        }
        int ans = 0;
        for (Map.Entry<Character, List<Integer>> m : map.entrySet()) {
            List<Integer> value = m.getValue();
            ans += value.size();
            if (value.size() == 1) {
                atom2.incrementAndGet();
                continue;
            } else {
                for (int i = 0; i < value.size() - 1; i++) {
                    Integer start = value.get(i);
                    for (int j = i + 1; j < value.size(); j++) {
                        Integer left = start; // 这行代码不能移动到上一行，每次循环这里必须都是start ****
                        Integer end = value.get(j);
                        Integer right = end;
                        while (left <= right) {
                            if (chars[left] == chars[right]) {
                                atom2.incrementAndGet();
                                left++;
                                right--;
                            } else {
                                break;
                            }
                        }
                        if (left > right) {
                            // System.out.println(s.substring(start, end + 1));
                            ans++;
                        }

                    }
                }
            }
        }
        return ans;
    }

}
